/*
 * @lc app=leetcode.cn id=402 lang=cpp
 *
 * [402] 移掉K位数字
 *
 * https://leetcode-cn.com/problems/remove-k-digits/description/
 *
 * algorithms
 * Medium (30.00%)
 * Likes:    518
 * Dislikes: 0
 * Total Accepted:    59.7K
 * Total Submissions: 181.2K
 * Testcase Example:  '"1432219"\n3'
 *
 * 给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
 * 
 * 注意:
 * 
 * 
 * num 的长度小于 10002 且 ≥ k。
 * num 不会包含任何前导零。
 * 
 * 
 * 示例 1 :
 * 
 * 
 * 输入: num = "1432219", k = 3
 * 输出: "1219"
 * 解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
 * 
 * 
 * 示例 2 :
 * 
 * 
 * 输入: num = "10200", k = 1
 * 输出: "200"
 * 解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
 * 
 * 
 * 示例 3 :
 * 
 * 
 * 输入: num = "10", k = 2
 * 输出: "0"
 * 解释: 从原数字移除所有的数字，剩余为空就是0。
 * 
 * 
 */
#include <string>
#include <stack>

using namespace std;

// @lc code=start
class Solution {
public:
    string removeKdigits(string num, int k) {
        stack<int> stk;
        for(char& c:num){
            while (stk.size()&&stk.top()>c-'0'&&k){
                stk.pop();
                k--;
            }
            stk.push(c-'0');
        }
        while(k--)
            stk.pop();
        string ret = "";
        while(stk.size()){
            ret.insert(ret.begin(), '0'+stk.top());
            stk.pop();
        }
        while(ret.size()>1&&ret[0]=='0')
            ret.erase(ret.begin());
        if(!ret.size()) ret = "0";
        return ret;
    }
};
// @lc code=end

